/*
Esempio 2.
Problema del minimo albero ricoprente.
(dalle slide SecondaParte_05_06.pdf, p. 75)

Problema:
minimize
	4x_12 + 3x_13 + x_23 + 10x_34 + 8x_35 + 9x_45 + 2x_48 + 2x_49 + 5x_89 + 2x_56 + 3x_57 + 5x_67 
subject to 
	x_12 + x_13 + x_23 + x_34 + x_35 + x_45 + x_48 + x_49 + x_89 + x_56 + x_57 + x_67 = 8 
	0 <= x <= 1 (per ogni x)
	
Questo problema, portato in forma standard per GLPK, diventa:
minimize
	4x_12 + 3x_13 + x_23 + 10x_34 + 8x_35 + 9x_45 + 2x_48 + 2x_49 + 5x_89 + 2x_56 + 3x_57 + 5x_67 
subject to 
	p = x_12 + x_13 + x_23 + x_34 + x_35 + x_45 + x_48 + x_49 + x_89 + x_56 + x_57 + x_67

bounds
	8 = p = 8
	
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "glpk.h"

void itoa(int, char[]);
void reverse(char[]);

int main(void) {

	/* Definizione delle strutture */
	glp_prob *lp;
	int ia[1+1000], ja[1+1000], i, j, a, current;
	double ar[1+1000], z, x[12], coef_obj[12] = { 4.0, 3.0, 1.0, 10.0, 8.0, 9.0, 2.0, 2.0, 5.0, 2.0, 3.0, 5.0 },
	       coef_p[12] = { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 },
	       coef_q[12] = { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0 };
	char varname[15], aux[5];
	
	// Inizializzazione variabili
	strcpy(varname, "x_");
	strcpy(aux, "");

	// Creazione del problema in memoria e assegnazione di un nome mnemonico
	lp = glp_create_prob();
	glp_set_prob_name(lp, "Esempio2");
	
	// Tipologia del problema
	glp_set_obj_dir(lp, GLP_MIN);
	
	// Aggiunta delle righe del problema (tante quante sono i vincoli, si creano variabili ausiliarie che le identificano)
	glp_add_rows(lp, 1);
	
	// Inizializza righe
	glp_set_row_name(lp, 1, "p");
	glp_set_row_bnds(lp, 1, GLP_FX, 8.0, 8.0);	// p
	
	// Aggiunta delle colonne del problema (tante quante sono le variabili)
	glp_add_cols(lp, 12);
	
	// Inizializza colonne (con coefficienti della funzione obiettivo)
	for (i = 0; i < 12; i++) {
		itoa(i+1, aux);
		strcat(varname, aux);
		glp_set_col_name(lp, i+1, varname);
		glp_set_col_bnds(lp, i+1, GLP_DB, 0.0, 1.0);
		glp_set_obj_coef(lp, i+1, coef_obj[i]);
		strcpy(varname, "x_");
	}

	for (a = 0; a < (glp_get_num_rows(lp) * glp_get_num_cols(lp)); a++) {
		ia[a+1] = 1;
		ja[a+1] = a+1;
		ar[a+1] = coef_p[a];
		current = a+1;			// Tenere traccia dell'ultimo valore di a(+1) per aggiunta successiva di vincolo violato
	}

	for (i = 0; i < (glp_get_num_rows(lp) * glp_get_num_cols(lp)); i++) {
		printf("ia[%d] = %d\tja[%d] = %d\tar[%d] = %.1f\n", i+1, ia[i+1], i+1, ja[i+1], i+1, ar[i+1]);
	}
	
	// Caricamento della matrice
	glp_load_matrix(lp, 12, ia, ja, ar);
	
	// Soluzione
	glp_simplex(lp, NULL);
	
	// Assegnazione dei valori alle variabili (per mostrare la soluzione)
	z = glp_get_obj_val(lp);
	for (i = 0; i < glp_get_num_cols(lp); i++) {
		x[i] = glp_get_col_prim(lp, i+1);
	}

	// Stampa su stdout del risultato
	printf("\nObj:\tz = %g;\n", z);
	for (i = 0; i < glp_get_num_cols(lp); i++) {
		printf("\tx%d = %g;\n", i+1, x[i]);
	}
	
	printf("Current: %d\n/****************** AGGIUNTA DI VINCOLO VIOLATO *******************/\n",current);

	glp_add_rows(lp, 1);
	glp_set_row_name(lp, 2, "p");
	glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 2.0);

	for (a = 0; a < (glp_get_num_rows(lp) * glp_get_num_cols(lp)); a++) {
		ia[current+a+1] = 2;
		ja[current+a+1] = a+1;
		ar[current+a+1] = coef_q[a];
	}

	for (i = 0; i < (glp_get_num_rows(lp) * glp_get_num_cols(lp)); i++) {
		printf("ia[%d] = %d\tja[%d] = %d\tar[%d] = %.1f\n", i+1, ia[i+1], i+1, ja[i+1], i+1, ar[i+1]);
	}

	glp_load_matrix(lp, offset_coeff, ia, ja, ar);
	
	// Soluzione
	glp_simplex(lp, NULL);
	
	// Assegnamento dei valori alle variabili (per mostrare la soluzione)
	z = glp_get_obj_val(lp);
	for (i = 0; i < glp_get_num_cols(lp); i++) {
		x[i] = glp_get_col_prim(lp, i+1);
	}

	// Stampa su stdout del risultato
	printf("\nObj:\tz = %g;\n", z);
	for (i = 0; i < glp_get_num_cols(lp); i++) {
		printf("\tx%d = %g;\n", i+1, x[i]);
	}

	glp_delete_prob(lp);
	
	return 0;
	
}

void itoa(int n, char s[])
 {
     int i, sign;
 
     if ((sign = n) < 0)  /* record sign */
         n = -n;          /* make n positive */
     i = 0;
     do {       /* generate digits in reverse order */
         s[i++] = n % 10 + '0';   /* get next digit */
     } while ((n /= 10) > 0);     /* delete it */
     if (sign < 0)
         s[i++] = '-';
     s[i] = '\0';
     reverse(s);
 }

void reverse(char s[])
 {
     int i, j;
     char c;
 
     for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
     }
 }
